package com.xmh.leetCode;

public class EightQueenGridding {

    /**
     * 棋盘大小
     */
    private static int Checkerboard_size = 8;

    /**
     * 皇后 棋格
     */
    private static QueenVo QUEEN_VO = new QueenVo(0, 0, Checkerboard_size);

    /**
     * 统计
     */
    private static int count = 0;

    public static void main(String[] args) {
        for (int i = 8; i < 16; i++) {
            long stratTime = System.currentTimeMillis();

            Checkerboard_size = i;

            QUEEN_VO = new QueenVo(0, 0, Checkerboard_size);
            /*
             * 初始化
             */
            init();

            putQueenAtRow(0);

            long endTime = System.currentTimeMillis();

            System.out.println(i + "皇后用时 : " + (endTime - stratTime) + " 结果 " + count);

            count = 0;
        }
    }

    private static void print(QueenVo queenVo) {
        for (int i = 0; i < Checkerboard_size; i++) {
            for (int j = 0; j < Checkerboard_size; j++) {
                QueenVo vo = find(queenVo, i, j);
                System.out.print(vo.isQueen() ? "1 " : "0 ");
            }
            System.out.println();
        }
    }

    /**
     * 利用递归和循环算出来到底有几种解
     *
     * @param row
     */
    private static void putQueenAtRow(int row) {
        QueenVo cache = QUEEN_VO;

        if (row == Checkerboard_size) {
            count++;
//			System.out.println("第" + count + "次解 \n");
//			print(QUEEN_VO);
            return;
        }
        for (int i = 0; i < row; i++) {
            cache = cache.getDown();
        }

        while (true) {
            if (cache == null) {
                break;
            }
            if (isSafety(cache)) {
                cache.setQueen(true);
                putQueenAtRow(row + 1);
                cache.setQueen(false);
            }
            cache = cache.getRight();
        }
    }

    /**
     * 检验是否安全
     *
     * @param QUEEN
     * @return
     */
    private static boolean isSafety(QueenVo QUEEN) {
        QueenVo cache = QUEEN;
        if (QUEEN == null) {
            return false;
        }
        while (true) {
            cache = cache.getUp();
            if (cache == null) {
                break;
            } else if (cache.isQueen()) {
                return false;
            }
        }

        cache = QUEEN;

        while (true) {
            if (cache.getUp() == null) {
                break;
            }

            cache = cache.getUp().getLeft();

            if (cache == null) {
                break;
            }
            if (cache.isQueen()) {
                return false;
            }
        }

        cache = QUEEN;

        while (true) {
            if (cache.getUp() == null) {
                break;
            }

            cache = cache.getUp().getRight();

            if (cache == null) {
                break;
            }
            if (cache.isQueen()) {
                return false;
            }
        }

        return true;
    }

    /**
     * 根据棋盘中的任意一个棋格找到复合下标的queenvo
     *
     * @param QUEEN
     * @param line
     * @param column
     * @return
     */
    private static QueenVo find(QueenVo QUEEN, int line, int column) {
        QueenVo vo = directionFor(QUEEN, true, true, line, column);
        if (vo == null) {
            vo = directionFor(QUEEN.getLeft(), false, false, line, column);
        }
        return vo;
    }

    private static QueenVo directionFor(QueenVo queenVo, boolean isRigth, boolean isDown, int line, int column) {
        if (queenVo == null) {
            return null;
        }
        if (queenVo.getColumn() == column && queenVo.getLine() == line) {
            return queenVo;
        }

        if (isRigth) {
            if (queenVo.getRight() != null) {
                return directionFor(queenVo.getRight(), isRigth, isDown, line, column);
            } else {
                if (isDown) {
                    return directionFor(queenVo.getDown(), !isRigth, isDown, line, column);
                } else {
                    return directionFor(queenVo.getUp(), !isRigth, isDown, line, column);
                }
            }
        } else {
            if (queenVo.getLeft() != null) {
                return directionFor(queenVo.getLeft(), isRigth, isDown, line, column);
            } else {
                if (isDown) {
                    return directionFor(queenVo.getDown(), !isRigth, isDown, line, column);
                } else {
                    return directionFor(queenVo.getUp(), !isRigth, isDown, line, column);

                }
            }
        }
    }

    public static int getCheckerboardSize() {
        return Checkerboard_size;
    }

    private static void init() {
        QUEEN_VO.setRight(new QueenVo(0, 1, Checkerboard_size));

        QueenVo rightCache = QUEEN_VO.getRight();

        QUEEN_VO.setDown(new QueenVo(1, 0, Checkerboard_size));

        QueenVo downCache = QUEEN_VO.getDown();

        for (int i = 0; i < Checkerboard_size; i++) {
            if (i != 0) {
                downCache.setRight(new QueenVo(i, 1, Checkerboard_size));

                rightCache = downCache.getRight();

                rightCache.setUp(rightCache.getLeft().getUp().getRight());

                if (i != Checkerboard_size - 1) {
                    downCache.setDown(new QueenVo(i + 1, 0, Checkerboard_size));

                    downCache = downCache.getDown();
                }
            }
            for (int j = 2; j < Checkerboard_size; j++) {
                rightCache.setRight(new QueenVo(i, j, Checkerboard_size));
                if (i != 0) {
                    rightCache.getRight().setUp(rightCache.getUp().getRight());
                }
                rightCache = rightCache.getRight();
            }
        }
    }

//	public static boolean isOdd(int i) {
//		return (i & 1) == 1;
//	}

}

class QueenVo {

    private int line = 0;

    private int column = 0;

    private QueenVo up = null;
    private QueenVo down = null;
    private QueenVo left = null;
    private QueenVo right = null;

    private boolean isQueen = false;

    public QueenVo(int line, int column, int size) {
        if (line < 0 || column < 0 || line > size - 1
                || column > size - 1) {
            throw new RuntimeException("行和列不能小于0!  并且不能大于7");
        }
        this.line = line;
        this.column = column;
    }

    public int getLine() {
        return line;
    }

    public void setLine(int line) {
        this.line = line;
    }

    public int getColumn() {
        return column;
    }

    public void setColumn(int column) {
        this.column = column;
    }

    public QueenVo getUp() {
        return up;
    }

    public void setUp(QueenVo up) {
        this.up = up;
        if (up.getDown() != this) {
            up.setDown(this);
        }
    }

    public QueenVo getDown() {
        return down;
    }

    public void setDown(QueenVo down) {
        this.down = down;
        if (down.getUp() != this) {
            down.setUp(this);
        }
    }

    public QueenVo getLeft() {
        return left;
    }

    public void setLeft(QueenVo left) {
        this.left = left;
        if (left.getRight() != this) {
            left.setRight(this);
        }
    }

    public QueenVo getRight() {
        return right;
    }

    public void setRight(QueenVo right) {
        this.right = right;
        if (right.getLeft() != this) {
            right.setLeft(this);
        }
    }

    public boolean isQueen() {
        return isQueen;
    }

    public void setQueen(boolean isQueen) {
        this.isQueen = isQueen;
    }

}
